use std::boxed::Box;
use std::option::Option;

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub next: Option<Box<Node<T>>>,
}

#[derive(Debug)]
pub struct LinkedList<T> {
    pub head: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    pub fn new(value: T) -> Self {
        Node { value, next: None }
    }
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList { head: None }
    }

    pub fn push_front(&mut self, value: T) {
        let mut node = Box::new(Node::new(value));
        if let Some(_) = self.head.as_mut() {
            node.next = self.head.take();
        }
        self.head = Some(node);
    }

    pub fn pop_front(&mut self) -> Option<T> {
        //match self.head.take() {
        //    None => None,
        //    Some(h) => {
        //        self.head = h.next;
        //        Some(h.value)
        //    },
        //}
        if let Some(h) = self.head.take() {
            self.head = h.next;
            return Some(h.value);
        }
        None
    }

    pub fn push_back(&mut self, value: T) {
        let node = Box::new(Node::new(value));
        match self.head.as_mut() {
            None => {
                self.head = Some(node);
            }
            Some(mut curr) => loop {
                match curr.next.as_ref() {
                    None => {
                        curr.next = Some(node);
                        break;
                    }
                    Some(_) => {
                        curr = curr.next.as_mut().unwrap();
                    }
                }
            },
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        match self.head.as_mut() {
            None => None,
            Some(mut node) => {
                while node.next.is_some() && node.next.as_ref().unwrap().next.is_some() {
                    node = node.next.as_mut().unwrap();
                }
                match node.next.as_mut() {
                    None => Some(self.head.take().unwrap().value),
                    Some(_) => Some(node.next.take().unwrap().value),
                }
                //None
            }
        }
        //None
    }

    pub fn peek_front(&self) -> Option<&T> {
        match self.head.as_ref() {
            None => None,
            Some(node) => Some(&node.value),
        }
    }

    pub fn peek_back(&self) -> Option<&T> {
        match self.head.as_ref() {
            None => None,
            Some(mut node) => loop {
                match node.next.as_ref() {
                    None => return Some(&node.value),
                    Some(nxt) => {
                        node = nxt;
                    }
                }
            },
        }
    }

    pub fn iter(&self) -> Iter<T> {
        Iter::new(&self.head)
    }

    pub fn into_iter(&mut self) -> IntoIter<T> {
        IntoIter::new(self.head.take())
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut::new(self.head.as_mut())
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        match self.head.take() {
            None => {}
            Some(mut node) => loop {
                match node.next.take() {
                    None => {
                        break;
                    }
                    Some(nxt) => {
                        node = nxt;
                    }
                }
            },
        }
    }
}

pub struct Iter<'a, T> {
    pub node: &'a Option<Box<Node<T>>>,
}

impl<'a, T> Iter<'a, T> {
    pub fn new(node: &'a Option<Box<Node<T>>>) -> Self {
        Iter { node }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        match self.node {
            None => None,
            Some(nxt) => {
                let result = Some(&nxt.value);
                self.node = &nxt.next;
                return result;
            }
        }
    }
}

pub struct IntoIter<T> {
    pub node: Option<Box<Node<T>>>,
}

impl<T> IntoIter<T> {
    pub fn new(node: Option<Box<Node<T>>>) -> Self {
        IntoIter { node }
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        match self.node.as_mut() {
            None => None,
            Some(_) => {
                let curr = self.node.take().unwrap();
                self.node = curr.next;
                Some(curr.value)
            }
        }
    }
}

pub struct IterMut<'a, T> {
    pub node: Option<&'a mut Box<Node<T>>>,
}

impl<'a, T> IterMut<'a, T> {
    pub fn new(node: Option<&'a mut Box<Node<T>>>) -> Self {
        IterMut { node }
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        match self.node.take() {
            None => None,
            Some(nxt) => {
                self.node = nxt.next.as_mut();
                Some(&mut (nxt.value))
            }
        }
    }
}

#[cfg(test)]
mod test {

    use super::*;

    #[test]
    fn test() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);

        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), None);

        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), None);
    }
}
